/*
	aco-netdesign -- Ant colony optimization solution to network design problem

	Copyright (C) 2008 Jeffrey Sharkey, http://jsharkey.org/
	
	Developed by Jeffrey Sharkey as part of his thesis work at Montana State
	University. His work was sponsored by the Western Transportation Institute,
	and was guided by advisor Doug Galarus. Other valuable guidance was
	provided by Dr. Bill Jameson and Gary Schoep. 

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.
	
	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.
	
	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <math.h>
#include <assert.h>
#include <stdio.h>

#include <iostream>
#include <sstream>
#include <fstream>

#include <string>
#include <list>
#include <map>
#include <vector>

using namespace std;

#include "graph.h"
#include "util.h"
#include "solver.h"
#include "aco.h"

#include <time.h>


// layer 0 is root
// layer 1 is "backbone"
// layer 2 is "relay"
// layer 3 is "node"


Graph* buildGraph(string file, double sens) {

// read in the graph in the given file
ifstream in(file.c_str(), ifstream::in);

Graph* g = new Graph();
Vertex* root = g->root;
root->layer = 0;

cout << "buildGraph: reading vertexes" << endl;

// walk through file and create all points
int max = -1;
while(in.good()) {
	int id;
	string type;
	double lat, lon;
	in >> id >> type >> lat >> lon;

	// stop at end of file, otherwise increment
	if(id == -1) break;
	id += 1;

	// stop if end of file, and keep track of maximum
	if(id > max) max = id;

	// create vertex and read in all sens values
	Vertex* v = new Vertex(lat, lon, 0);
	v->id = id;
	v->sens = new double[id];
	for(int i = 0; i < id; i++) {
		in >> v->sens[i];
	}

	// set tower layer correctly
	if(type == "backbone") {
		v->layer = 1;
		// add link back to backbone
		g->addEdge(new Edge(v, root, 0));
	} else if(type == "relay") {
		v->layer = 2;
	} else if(type == "node") {
		v->layer = 3;
		v->terminal = true;
		v->bandwidth = 10;
	}

	g->addVertex(v);

}

cout << "buildGraph: adding edges" << endl;

// walk through all towers and create links if they pass sens
for(int i = 1; i <= max; i++) {
	Vertex* v = g->vertexes[i];
	for(int j = 1; j < v->id; j++) {
		// skip if we are denied or outside of sens range
		if(v->sens[j-1] == 1024) continue;
		if(v->sens[j-1] < sens) continue;

		// add edge with specific cost
		g->addEdge(new Edge(v, g->vertexes[j], 1));
	}
}

cout << "buildGraph: finished with graph having |V|=" << g->vertexes.size() << " and |E|=" << g->edges.size() << endl << endl;


return g;

}









#define RESET_LATER 10240

// layer 0 is root
// layer 1 is "backbone"
// layer 2 is "relay"
// layer 3 is "node"



Graph* buildGraphClone(string file, double sens) {

// read in the graph in the given file
ifstream in(file.c_str(), ifstream::in);

Graph* g = new Graph();
Vertex* root = g->root;
root->layer = 0;

map<int,Vertex*> terminal;

cout << "buildGraphClone: reading vertexes" << endl;

// walk through file and create all points
int max = -1;
while(in.good()) {
	int id;
	string type;
	double lat, lon;
	in >> id >> type >> lat >> lon;

	// stop at end of file, otherwise increment
	if(id == -1) break;
	id += 1;
//if(id > 200) break;

	// stop if end of file, and keep track of maximum
	if(id > max) max = id;

	// create vertex and read in all sens values
	Vertex* v = new Vertex(lat, lon, 0);
	v->id = id;
	v->sens = new double[id];
	for(int i = 0; i < id; i++) {
		in >> v->sens[i];
	}

	// set tower layer correctly
	if(type == "backb") {
		v->layer = 1;
		v->cost = 10;
		// add link back to backbone
		g->addEdge(new Edge(v, root, 0.001, 10240, -10));
	} else if(type == "relay") {
		v->layer = 2;
		v->cost = 2;

		// create terminal vertex for specific cases
		Vertex* u = new Vertex(lat, lon, 0);
		u->id = id;
		u->layer = 3;
		u->terminal = true;
u->bandwidth = 128;
		terminal[id] = u;

	} else if(type == "node") {
		v->layer = 3;
		v->terminal = true;
		// TODO: assign bandwidth as required
	}

	g->addVertex(v);

}

cout << "buildGraph: adding edges" << endl;

// walk through all towers and create links if they pass sens
for(int i = 1; i <= max; i++) {
	Vertex* v = g->vertexes[i];
	for(int j = 1; j < v->id; j++) {
		// skip if we are denied or outside of sens range
		if(v->sens[j-1] == 1024) continue;
		if(v->sens[j-1] < sens) continue;

		double margin = v->sens[j-1];

		Vertex* w = g->vertexes[j];

		// add edge with specific cost
		if((v->layer == 1 && w->layer == 2) || (v->layer == 2 && w->layer == 1)) {
			g->addEdge(new Edge(v, w, 5, 5120, margin));
		} else if(v->layer == 2 && w->layer == 2) {
			// connect relaying along this layer
			g->addEdge(new Edge(v, w, 1, 1024, margin));

			// create edges from relay layer down to all terminal nodes
			g->addEdge(new Edge(g->vertexes[i], terminal[j], 0.001, 256, margin));
			g->addEdge(new Edge(g->vertexes[j], terminal[i], 0.001, 256, margin));
		}
			
	}
}

// walk through terminal, set correct ids, and insert into graph
map<int,Vertex*>::iterator it;
for(it = terminal.begin(); it != terminal.end(); it++) {
	Vertex* v = (*it).second;
	v->id = ++max;
	g->addVertex(v);
}

cout << "buildGraph: finished with graph having |V|=" << g->vertexes.size() << " and |E|=" << g->edges.size() << endl << endl;


return g;

}












Graph* buildEuclid(int terminal, int backbone, double radius, bool silent) {

Tagged::nextid = 0;

Graph* g = new Graph();
Vertex* root = g->root;
root->layer = 0;

if(!silent) cout << "buildEuclid: setting terminal nodes across space" << endl;
for(int i = 0; i < terminal; i++) {
	double x = (double)i / (double)terminal;

	Vertex* term = new Vertex(x, x, 0);
	term->terminal = true;
	term->layer = 3;
	g->addVertex(term);

	Vertex* relay = new Vertex(x, x, 2);
	relay->terminal = false;
	relay->layer = 2;
	g->addVertex(relay);
}


if(!silent) cout << "buildEuclid: adding backbone relays" << endl;
for(int i = 0; i < backbone; i++) {
//	double x = ((double)rand() / (double)RAND_MAX),
//		y = ((double)rand() / (double)RAND_MAX);	
	double x = mt_rand(),
		y = mt_rand();

	Vertex* back = new Vertex(x, y, 10);
	back->terminal = false;
	back->layer = 1;
	g->addVertex(back);
}





if(!silent) cout << "buildEuclid: adding edges" << endl;
TimeRemaining* tr = new TimeRemaining(g->steiner.size(), 8);
tr->silent = silent;

// add any edges for each steiner node
list<Vertex*>::iterator v;
for(v = g->steiner.begin(); v != g->steiner.end(); v++) {
//	double noderadius = radius * ((double)rand() / (double)RAND_MAX);
	double noderadius = radius * mt_rand();

	// add edges back to root node if backbone
	if((*v)->layer == 1)
		g->addEdge(new Edge((*v), root, 0.01));

	// connect to any other steiner nodes in range
	list<Vertex*>::iterator u;
	for(u = g->steiner.begin(); u != g->steiner.end(); u++) {
		if((*u)->id == (*v)->id) continue;
		if((*v)->euclidianDistance((*u)) > noderadius) continue;
		if(g->edgeExists((*u), (*v))) continue;
		
		// handle linking relay to backbone
		if(((*u)->layer == 1 && (*v)->layer == 2) || ((*u)->layer == 2 && (*v)->layer == 1))
			g->addEdge(new Edge((*u), (*v), 5));

		// handle relay linking between roadside towers
		if((*u)->layer == 2 && (*v)->layer == 2)
			g->addEdge(new Edge((*u), (*v), 1));


	}

	if((*v)->layer != 2) continue;

	// connect all relays down to terminal layer
	for(u = g->terminal.begin(); u != g->terminal.end(); u++) {
		if((*u)->root) continue;
		if((*v)->euclidianDistance((*u)) > noderadius) continue;

//		g->addEdge(new Edge((*u), (*v), 0.01 * ((double)rand() / (double)RAND_MAX)));
		g->addEdge(new Edge((*u), (*v), 0.01 * mt_rand()));

	}

	tr->increment();

}

delete tr;

cout << "buildEuclid: finished with graph having |V|=" << g->vertexes.size() << " and |E|=" << g->edges.size() << endl << endl;

return g;

}












#define BUILDLOOKUP false
#define BUILDAPPROX false






int main(int argc, char** argv) {




//srand(4);
// use default mt init seed
mt_init(5489UL);

string path = "/students/jsharkey/libprop/output/";
string example = "mar20-191";
//mar20-191


cout << "## WORKING WITH " << example << endl;

// read in graph from given file
Graph* g = buildGraphClone(string(path+example+".txt"), -95);

ofstream out_visual(string(example+".moo.graphml").c_str(), ofstream::out);
g->saveVisual(out_visual);
out_visual.close();

cout << "DUMPED " << string(example+".moo.graphml") << endl;

exit(0);


cout << "main: building adjacency graph" << endl;
g->buildAdjacent();
g->perturbCosts();


// build and save a lookup table, or load an existing one
Lookup* look;
if(BUILDLOOKUP) {
	cout << endl << "main: building lookup table" << endl;
	look = buildFloyd(g);
	ofstream out_lookup(string(path+example+".lookup").c_str(), ofstream::out);
	look->save(out_lookup);
	exit(0);
} else {
	cout << endl << "main: loading existing lookup table" << endl;
	ifstream in_lookup(string(path+example+".lookup").c_str(), ifstream::in);
	look = new Lookup(g);
	look->load(in_lookup);
}


if(BUILDAPPROX) {

	SolverApprox* solverApprox = new SolverApprox(g, look);
	Solution* sApprox = solverApprox->singleSolution();

	cout << endl << "## \t\tapprox.cost\t" << sApprox->cost() << "\t|V|\t" << sApprox->vertexes.size() << "\t|E|\t" << sApprox->edges.size() << endl;

	//sApprox->saveSimple(g, "output.approx.kml");
	//sApprox->save(g, "output.approx.kml");
	//sApprox->saveRaw(g, "output.approx.txt");

	delete sApprox;
	delete solverApprox;
	exit(0);
}



//cout << "main: solving using aco..." << endl;

// 52 seconds for generation of 24
// 2.2 seconds for each solution

// 8*16*2*20 (0.2 to 4 with 0.2 steps)

// used 3,1,0.9 before

SolverACO::alphaHeur = 30;
SolverACO::alphaPher = 1;
SolverACO::alphaRand = 1; //0.9
SolverACO::alphaPref = 1;



// actual simple solve



SolverACO* solverACO = new SolverACO(g, look);
SolutionACO* sACO = solverACO->fullSolve(8,16); //8,32 or 32,512
				// used 64,512 to prove convergence
				// used 16,64 for most thesis stuff
	
cout << "## heur\t30\taco.cost\t" << sACO->cost() << "\t|V|\t" << sACO->vertexes.size() << "\t|E|\t" << sACO->edges.size() << "\tgen\t" << solverACO->generations << endl;

sACO->saveVisual(g, "output."+example+".beforels.graphml");


// perform postprocessing local search to find better solutions
sACO->localSearch(g);


sACO->save(g, "output."+example+".aco.kml");
sACO->saveVisual(g, "output."+example+".graphml");

delete sACO;
delete solverACO;


exit(1);















// first batch was 0.1 to 4 with step 0.1
// second batch was 4 to 8 with step 0.5

// usually using 0-4 with 0.1 steps

// started at 1.5-50 for output-mar5-sf0
for(double alpha = 1.5; alpha <= 100; ) {
//for(double alpha = 300; alpha <= 600; ) {

// change how much alpha is updated
if(alpha < 1) alpha += 0.1;  //0.1
else if(alpha < 2) alpha += 0.2; //0.2
else if(alpha < 10) alpha += 1; //1
else if(alpha < 100) alpha += 10; //10
else if(alpha < 300) alpha += 20; //20
else alpha += 10;

if(alpha > 55) alpha = 120;


//for(double alpha = 4; alpha <= 40; alpha += 2) {
for(int i = 0; i < 15; i++) {

//srand(4);
Tagged::nextid = 0;

//cout << endl << "look->get(694,204)=" << look->get(694,204) << endl;
//cout << endl << "loaded!" << endl;


SolverACO::alphaHeur = alpha;
//SolverACO::alphaHeur = 50;



	SolverACO* solverACO = new SolverACO(g, look);
//solverACO->silent = true;
	SolutionACO* sACO = solverACO->fullSolve(16,64); //8,32 or 32,512
				// used 64,512 to prove convergence
	

	cout << "## heur\t" << alpha << "\taco.cost\t" << sACO->cost() << "\t|V|\t" << sACO->vertexes.size() << "\t|E|\t" << sACO->edges.size() << "\tgen\t" << solverACO->generations << endl;

//	sACO->save(g, "output."+example+".aco.kml");
//	sACO->saveSimple(g, "output."+example+".aco-simple.kml");
//	sACO->saveRaw(g, "output.aco.txt");
//	sACO->savePheromones("pher-feb4");
//exit(1);

	delete sACO;
	delete solverACO;

}
}







cout << "main: finished" << endl;


}


























/**********************************************************************  timing tests



// based on stdin, generate a graph with a given number of nodes

int n = atoi(argv[1]);

Graph* g = buildEuclid(n, n/10, 0.15, true);

g->buildAdjacent();
g->perturbCosts();

Lookup* look = buildFloyd(g);


for(int i = 0; i < 2; i++) {

clock_t start,finish;

start=clock();

SolverACO* solverACO = new SolverACO(g, look);
solverACO->silent = true;
SolutionACO* sACO = solverACO->fullSolve(10, 100);
cout << "using 50";

finish=clock();

double time = (double(finish)-double(start))/CLOCKS_PER_SEC;


cout << endl << endl << "---- |V|=" << g->vertexes.size() << "\t|E|=" << g->edges.size() << "\ttime=" << time << endl << endl;

}




exit(0);






********************************************************************* ratio tests over euclidian



// generate pile of euclidian graphs of varying terminal size and record best aco and approx solutions

for(int n = 9; n <= 10; n++) {
for(int i = 0; i < 5; i++) {

Graph* g = buildEuclid(50*n, 5*n, 0.15, true);

g->buildAdjacent();
g->perturbCosts();


Lookup* look = buildFloyd(g);


//cout << endl << "main: solving using approx" << endl;
SolverApprox* solverApprox = new SolverApprox(g, look);
Solution* sApprox = solverApprox->singleSolution();
cout << endl << "---- approx.cost=" << sApprox->cost() << "\t|V|=" << sApprox->vertexes.size() << "\t|E|=" << sApprox->edges.size() << endl;

//sApprox->saveSimple(g, "output.approx.kml");
//sApprox->save(g, "output.approx.kml");
//sApprox->saveRaw(g, "output.approx.txt");

delete sApprox;
delete solverApprox;





for(int j = 0; j < 5; j++) {

SolverACO* solverACO = new SolverACO(g, look);
solverACO->silent = true;
SolutionACO* sACO = solverACO->fullSolve(10, 8);

cout << "---- aco.cost=" << sACO->cost() << "\t|V|=" << sACO->vertexes.size() << "\t|E|=" << sACO->edges.size() << "\tgen=" << solverACO->generations << endl;

//sACO->saveSimple(g, "output.aco.kml");
//sACO->save(g, "output.aco.kml");
//sACO->saveRaw(g, "output.aco.txt");

delete sACO;
delete solverACO;

}




delete g;



}
}





cout << "main: finished" << endl;

**********************************************************************/
